package algorithm.mst.kruskal;

/**
 * @ author : HyoJoo-W
 * @ createDate : 2021-06-07 19:41
 * @ Description : (1) 根据边的权值排序
 * (2) 添加最小权值边时不形成回路(终点不同)
 */
public class KruskalAlgo
{
    private int numOfEdges;
    private char[] vertexes;
    private int[][] matrix;
    private static final int INF = 10000;

    public KruskalAlgo(char[] vertexes, int[][] matrix)
    {
        this.vertexes = vertexes;
        this.matrix = matrix;
        this.numOfEdges = countNumOfEdges();
    }

    private void sortEdges(Edge[] edges)
    {
        for (int i = 0; i < edges.length - 1; i++)
        {
            for (int j = 0; j < edges.length - 1 - i; j++)
            {
                if (edges[j].weight > edges[j + 1].weight)
                {
                    Edge temp = edges[j];
                    edges[j] = edges[j + 1];
                    edges[j + 1] = temp;
                }
            }
        }
    }

    /**
     * @Description 获取ch在顶点数组中的索引
     * @param ch: 顶点的数据域字符
     * @return int
     **/
    private int getPosition(char ch)
    {
        for (int i = 0; i < vertexes.length; i++)
        {
            if (vertexes[i] == ch)
            {
                return i;
            }
        }
        return -1;
    }

    private Edge[] getEdges()
    {
        int index = 0;
        Edge[] edges = new Edge[numOfEdges];
        for (int i = 0; i < vertexes.length; i++)
        {
            for (int j = i + 1; j < vertexes.length; j++)
            {
                if (matrix[i][j] != INF)
                {
                    edges[index++] = new Edge(vertexes[i], vertexes[j], matrix[i][j]);
                }
            }
        }
        return edges;
    }

    private int countNumOfEdges()
    {
        for (int[] rows : this.matrix)
        {
            for (int j = 0; j < this.matrix.length; j++)
            {
                if (rows[j] != INF)
                {
                    numOfEdges++;
                }
            }
        }
        return numOfEdges / 2;
    }

    /**
     * @Description 获取索引为index的字符顶点的终点
     * @param ends: 记录各个顶点的终点,在遍历过程中逐步形成
     * @return int
     **/
    private int getEnd(int[] ends, int index)
    {
        while (ends[index] != 0)
        {
            index = ends[index];
        }
        return index;
    }

    public void kruskal()
    {
        int index = 0;
        //记录已有mst中的顶点在mst中的终点
        int[] ends = new int[numOfEdges];

        //结果数组
        Edge[] res = new Edge[numOfEdges];

        //1. 边排序
        Edge[] edges = this.getEdges();
        sortEdges(edges);

        //2. 添加(判断回路)
        for (int i = 0; i < numOfEdges; i++)
        {
            //获取第i条边的起点
            int iStart = this.getPosition(edges[i].start);
            int iEnd = this.getPosition(edges[i].end);

            int mstStart = this.getEnd(ends,iStart);
            int mstEnd = this.getEnd(ends,iEnd);
            if (mstStart != mstEnd)
            {
                //不构成回路
                ends[mstStart] = mstEnd;
                res[index++] = edges[i];
            }
        }

        System.out.println("mst...");
        int totalWeight = 0;
        for (int i = 0; i < index; i++)
        {
            totalWeight += res[i].weight;
            System.out.println(res[i]);
        }
        System.out.println("totalWeight = " + totalWeight);
        //return res;

    }


    public static void main(String[] args)
    {
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weight = new int[][]{
                {10000, 5, 7, 10000, 10000, 10000, 2},
                {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000},
                {10000, 9, 10000, 10000, 10000, 4, 10000},
                {10000, 10000, 8, 10000, 10000, 5, 4},
                {10000, 10000, 10000, 4, 5, 10000, 6},
                {2, 3, 10000, 10000, 4, 6, 10000},
        };
        KruskalAlgo kruskalAlgo = new KruskalAlgo(data, weight);

       kruskalAlgo.kruskal();

    }
}

class Edge
{
    public char start;
    public char end;
    public int weight;

    public Edge(char start, char end, int weight)
    {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString()
    {
        return "Edge{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}
